package com.spirng.leetcode.day06;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Test513 {
    private int Depth=-1;
    private int val=0;
    public int findBottomLeftValue(TreeNode root) {
        val=root.val;
        findLeftValue(root,0);
        return val;
    }
    public void findLeftValue(TreeNode root,int depth) {
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            if(depth>Depth){
                val=root.val;
                Depth=depth;
            }
        }
        if(root.left!=null){
            depth++;
            findLeftValue(root.left,depth);
            depth--;//回溯过程
        }
        if(root.right!=null){
            depth++;
            findLeftValue(root.right,depth);
            depth--;
        }

    }
    public int findBottomLeftValue1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return 0;
        }
        int leftValue=0;
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if(i==0){
                   leftValue=node.val;
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        return leftValue;
    }
}
